#pragma once
#include <bits/stdc++.h>
using namespace std;

class KamaCoder47 {
 public:
  struct Edge {
    int to;   // 连接的下一个顶点
    int val;  // 权重
    Edge(int t, int v) : to(to), val(val) {}
  };
  class mycmp {
   public:
    // 重载小顶堆的比较函数
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
      return a.second > b.second;  // 意味着a的优先级低于b，即a会被放在b的下面
      // 较小的second值会优先被放在堆顶，从而实现小顶堆
    }
  };
  // 优先队列中存放  pair<节点，节点的权重>
  priority_queue<pair<int, int>, vector<pair<int, int>>, mycmp> pq;
  // 小顶堆
  int run();
  int run2();
};

// 构造边类型
struct Edge {
  int left, right, val;
  Edge(int _left, int _right, int _val)
      : left(_left), right(_right), val(_val) {}
};

class KamaCoder53 {
 public:
  void init();

  int find(int x);

  void join(int x, int y);

  int run();
  int krushkalrun();

  int m_n = 50;
  vector<int> father = vector<int>(m_n);
};

class KamaCoder94 {
 public:
  struct Edge {                             // 邻接表
    int to;                                 // 节点
    int val;                                // 边的权重
    Edge(int t, int v) : to(t), val(v) {};  // 构造函数
  };

  int run();
  int run2();
};

class KamaCoder95 {
 public:
  const int MAX_INT = 23154;

  int run();
  // int run2();
};

class KamaCoder97 {
 public:
  const int MAX_INT = 23154;

  int run();
  int run2();
};

class KamaCoder102 {
 public:
  int count;
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右

  // 深度搜索
  void dfs(vector<vector<int>>& grid, int x, int y);
  // 广度搜索
  void bfs(vector<vector<int>>& grid, int x, int y);

  int run();
};

class KamaCoder103 {
 public:
  // int count;
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右

  // 深度搜索
  void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited,
           int x, int y);
  // 广度搜索
  // void bfs(vector<vector<int>>&grid ,int x,int y);

  int run();
};

class KamaCoder104 {
 public:
  int count;
  int n, m;
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右

  // 深度搜索
  void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x,
           int y, int mark);
  // 广度搜索
  // void bfs(vector<vector<int>>&grid ,int x,int y);

  int run();
};

class KamaCoder105 {
 public:
  void dfs(vector<list<int>>& graph, vector<bool>& visited, int key);
  int run();
};

class KamaCoder106 {
 public:
  int run();
};

class KamaCoder107 {
 public:
  // 声明函数

  void init(int n);
  int find(int x);
  void join(int x, int y);
  bool isSame(int x, int y);

  int run();
  int m_n = 300;
  // 定义并查集的数组
  vector<int> father = vector<int>(m_n);
};

class KamaCoder108 {
 public:
  // 声明函数

  void init(int n);
  int find(int x);
  void join(int x, int y);
  bool isSame(int x, int y);

  int run();
  int m_n = 300;
  // 定义并查集的数组
  vector<int> father = vector<int>(m_n);
};

class KamaCoder109 {
 public:
  // 定义并查集的数组
  vector<int> father = vector<int>(1005);
  int m_n;

  KamaCoder109() : father(1001, 0), m_n(0) {}
  // 声明函数
  void init(int n);
  int find(int x);
  void join(int x, int y);
  bool isSame(int x, int y);
  bool isTreeAfterRemoveEdge(vector<vector<int>>& edges, int index);
  void getRmoveEdge(vector<vector<int>>& edges);
  int run();
};

class KamaCoder110 {
 public:
  int run();
};

class KamaCoder117 {
 public:
  int run();
};

class KamaCoder126 {
 public:
  int moves[1001][1001];  // 移动的棋盘 也记录步数情况
  int end_x, end_y;

  struct Knight {
    int x, y;
    int g, h, f;
    // 重载运算符，从小到大排序
    bool operator<(const Knight& k) const { return k.f < f; }
  };

  // 欧拉距离
  int Heuristic(const Knight& k) {
    // 统一没有开根号
    return (k.x - end_x) * (k.x - end_x) + (k.y - end_y) * (k.y - end_y);
  }

  // 马走日
  const int dir[8][2] = {-2, -1, -2, 1,  -1, 2,  1,  2,
                         2,  1,  2,  -1, 1,  -2, -1, -2};

  priority_queue<Knight> que;

  void astar(const Knight& k);

  int run2();
};

class KamaCoder143 {
 public:
  // 定义二叉树
  struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
  };
  // 创建二叉树
  TreeNode* createTrees(vector<string>& vecs);
  // 查找路径
  int findPath(TreeNode* root);
  // 运行
  int run();
  int result;
};

class KamaCoder138 {
 public:
  int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};  // 上下左右
  int run();
};